package pro.softzhang.algo.lc1000;

import java.util.*;

/**
 *
 */
public class LC1054_DistantBarcodes {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        /**
         * 1 2 2
         * 1 1 2
         * @param barcodes
         * @return
         */
        public int[] rearrangeBarcodes(int[] barcodes) {
            int n = barcodes.length;
            Integer[] t = new Integer[n];
            int mx = 0;
            for (int i = 0; i < n; ++i) {
                t[i] = barcodes[i];
                mx = Math.max(mx, barcodes[i]);
            }
            int[] cnt = new int[mx + 1];
            for (int x : barcodes) {
                ++cnt[x];
            }
            Arrays.sort(t, (a, b) -> cnt[a] == cnt[b] ? a - b : cnt[b] - cnt[a]);
            int[] ans = new int[n];
            for (int k = 0, j = 0; k < 2; ++k) {
                for (int i = k; i < n; i += 2) {
                    ans[i] = t[j++];
                }
            }
            return ans;
        }
    }
}
